//
// Description: 54. 螺旋矩阵
// Created by Loading on 2021/9/12.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> spiralOrder(vector<vector<int>> &matrix) {
    int m = (int) matrix.size();
    int n = (int) matrix[0].size();
    // 访问标记数组
    bool visit[m][n];
    memset(visit, false, sizeof visit);

    vector<int> res(m * n);
    // x y 坐标偏移数组
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};

    for (int i = 0, x = 0, y = 0, d = 0; i < m * n; ++i) {
        res[i] = matrix[x][y];
        visit[x][y] = true;
        int next_x = x + dx[d], next_y = y + dy[d];
        // 走到尽头
        if (next_x >= m || next_x < 0 || next_y >= n || next_y < 0 || visit[next_x][next_y]) {
            // 更改方向
            d = (d + 1) % 4;
            next_x = x + dx[d];
            next_y = y + dy[d];
        }
        // 更新 x y
        x = next_x;
        y = next_y;
    }

    return res;
}

int main() {
    vector<vector<int>> matrix = {{1, 2,  3,  4},
                                  {5, 6,  7,  8},
                                  {9, 10, 11, 12}};
    vector<int> res = spiralOrder(matrix);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}
